This invention relates to simulation of linear feedback shift registers (LFSR). More particularly, it relates to the use of linear superposition properties and state skipping to determine the Nth state of the LFSR.
Several applications require the simulation of large LFSRs to determine the state of the machine. Examples of such applications include password generation, BIST convergent signature analysis, secure credit card, integrated system security, and diverse encryption encoding and decoding systems.
A linear feedback shift register has may uses in testing, communication, and encryption application. In the present invention, it is used to generate pseudo random binary sequences or patterns, and may be configured as a multiple input signature register (MISR) or single input signature register (SISR) to compress data and generate signatures.
Referring to FIGS. 1 and 2, an LFSR is a special configuration of a linear circuit into a special form of shift register or counter. These circuits require only a clock input 90, making them autonomous, and include three basic logic components:
1. Latch or D-type flip-flop or a unit delay 96, 98.
2. Exclusive-OR (XOR) or modulo-2 adder 92, 94.
3. Modulo-2 scalar multiplier 84, 86.
An LFSR circuit 80, 82 can take either of two equivalent or dual forms: the standard generic LFSR 80 of FIG. 1 or the modular generic LFSR 82 of FIG. 2. Each cell 96 (L1, L2, L3, . . . , Ln-1, Ln) and 98 (L1, . . . , Ln-3, Ln-2, Ln-1, Ln) in each type has the same structure and is replicated for the desired length n of the LSFR 80, 82. Modulo-2 scalar multiplier C1 to Cn-1 84, 94 is either 0 or 1, which results in a connection or no-connection for the feedback signal 88, 90, respectively.
Some of the characteristics of an LFSR are its length or number of cells (n), the feedback configuration or values of each Ci, and the initial state of the circuit. A maximal length LFSR is a circuit that cycles through 2n−1 unique states when initialized with a non-zero value. The maximum number of unique states of an n length shift register is 2n, so a maximal length LFSR cycles through all the possible states except when initialized to zero. A non-maximal length LFSR also cycles through a sub-set of 2n states depending on the initial seed or initial value.
FIG. 3 illustrates the truth table for a modulo-2 adder, and a simple example of an LFSR 74 is shown in FIG. 4. The LFSR of FIG. 4 is a simple three stage (n=3) maximal length configured LFSR. In this case the outputs from latches L2 and L3 are XORed and fed back to L1. The state table 78 of FIG. 4 and state diagram 76 of FIG. 5 illustrate the sequence of states that LFSR 74 cycles through after being initialized to all “1”s at state S0. The binary output sequence 1110010 is seven bits before it starts repeating.
The length of the simple circuit of FIG. 4 can be extended to provide long sequences of binary pseudo random numbers. For example, a 32-bit maximal length LFSR can cycle for over four billion states before repeating. Furthermore, by selecting the appropriate feedback parameters for the LFSR, one can generate unique sequences for each configuration.
Referring to FIGS. 6 and 7, the general theory of operation and characteristics of the LFSR when used for data compression as a signature generation register will be described. There are many data compression algorithms and hardware implementations that can be used to generate signatures, but the use of an LFSR as a single input signature register (SISR) or multiple input signature register (MISR) has the advantage that it can be easily implemented in both hardware and software with low aliasing probability and a high degree of customization flexibility.
In a signature register, one or more bits of input data are XORed on every Nth shift cycle of the LFSR. Typically, data is clocked into the LFSR on every shift cycle. The LFSR can be configured as an SISR or MISR. The single input configuration is usually used to serially compress long data bit strings, while the multiple input configuration can be used for simultaneous parallel compression of multiple bit groups such as a byte or word of input data as shown in FIGS. 6 and 7, respectively.
The data input(s) to the LFSR can be XORed at any point in to the circulating shift register. The maximum number of possible single inputs for an N-length LFSR is N. If the number of inputs is greater than N, the length of the LFSR may be increased, or subsets of inputs XORed for each MISR input. The output or signature of the SISR or MISR is usually the final state of the LFSR after all the data has been compressed or shifted into the LFSR. The length of the output signature can be the whole length of the LFSR or a truncated portion of N.
The MISR or SISR can be further customized by selecting the initial seed or state prior to data compression, selecting the feedback configuration, input structure, number of shift cycles per data bit(s), and lengths of the LFSR. The length of the LFSR can be optimized for a particular system platform (i.e. 32-bits, 64-bits, 128-bits, 256-bits, or any bit length) or tailored for security robustness.
FIG. 8 illustrates an example of a 2-input 5-stage MISR with the associated state table of FIGS. 9 and 10 for two input data sequences, FIG. 9 for the case where input 1 and input 2 are both 0, and FIG. 10 for the case where input values in1 and in2 may take on various sequences of 0 and 1 for each of the 31 states.
As a computer's ability to resolve encrypted data improves, the need to run LSFRs with a large number of cycles increases. The problem, then, with a typical LSFR, is that if a large number of cycles are to be run, it will take a considerable length of time.